package xyz.naokeziteng.leetcode;

import java.awt.*;
import java.util.Arrays;

/**
 * @author hawk
 * @date 2022/6/7
 * @desc 826题：安排工作以达到最大收益
 **/
public class MaxProfitAssignment {


    public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int allProfit = 0;
        for (int i = 0; i < worker.length; i++) {
            int tmpProfit = 0;
            //工作难度遍历
            for (int j = 0; j < difficulty.length; j++) {
                if (difficulty[j] <= worker[i]
                        && profit[j] > tmpProfit) {
                    tmpProfit = profit[j];
                }
            }
            allProfit += tmpProfit;
        }


        return allProfit;
    }


    public static int maxProfitAssignmentV2(int[] difficulty, int[] profit, int[] worker) {

        int N = difficulty.length;
        Point[] jobs = new Point[N];
        for (int i = 0; i < N; ++i)
            jobs[i] = new Point(difficulty[i], profit[i]);
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        Arrays.sort(worker);

        int ans = 0, i = 0, best = 0;
        for (int skill: worker) {
            while (i < N && skill >= jobs[i].x)
                best = Math.max(best, jobs[i++].y);
            ans += best;
        }

        return ans;
    }


    public static void main(String[] args) {
        int[] difficulty = {68, 35, 52, 47, 86};
        int[] profit = {67, 17, 1, 81, 3};
        int[] worker = {92, 10, 85, 84, 82};


        System.out.println(maxProfitAssignmentV2(difficulty, profit, worker));
    }
}
